#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void heapInit(sl* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = p->size = 0;
}
void heapdestroy(sl* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->size = 0;
}
void adjust(int* p, int n,int child)
{
	assert(p);
	int parent = (child - 1) / 2;
	while (1) 
	{
		if (p[child] > p[parent])
		{
			heapswap(&p[child], &p[parent]);
			child = parent;
			parent= (child - 1) / 2;
		}
		else break;
	}
}
void heapswap(dataty* p, dataty* q)
{
	dataty tmp = *p;
	*p = *q;
	*q = tmp;
}
void heappush(sl* p, dataty x)
{
	assert(p);
	if (p->size == p->capacity)
	{
		int new = p->capacity == 0 ? 4 : p->capacity * 2;
		sl* q = (sl*)realloc(p->a,sizeof(sl) * new);
		p->a = q;
		p->capacity = new;
	}
	p->a[p->size] = x;
	p->size++;
	adjust(p->a, p->size, p->size - 1);
}
void heapprintf(sl* p)
{
	int i = p->size-1;
	while (i >= 0)
	{
		printf("%d ", p->a[i]);
		i--;
	}
}
bool heapempty(sl* p)
{
	assert(p);
	return p->size == 0;
}
int heapsize(sl* p)
{
	assert(p);
	return p->size;
}
void heappop(sl* p)
{
	assert(p);
	assert(!heapempty(p));
	heapswap(&p->a[0], &p->a[p->size - 1]);
	p->size--;
	justdown(p->a, p->size, 0);
}
void justdown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (a[child + 1] < a[child] && child+1 < n)
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			heapswap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}